package algorithm;

/**
 * @Author wangtengyu
 * @Create 2018-03-27-15:39
 * 快速排序
 */
public class QuickSort {

    /**
     * 交换数组元素
     *
     * @param array
     * @param i
     * @param j
     */
    private static void swap(int array[], int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    /**
     * 进行排序
     *
     * @param array
     */
    public static void sort(int array[]) {
        quickSort(array, 0, array.length - 1);
    }


    private static void quickSort(int array[], int left, int right) {
        if (right<=left) {
            return;
        } else {
            int partition = partition(array, left, right);
            quickSort(array,left,partition-1);
            quickSort(array,partition+1,right);
        }


    }

    /**
     * 分割算法 分割成两个数组
     *
     * @param array
     * @param left
     * @param right
     * @return
     */
    private static int partition(int[] array, int left, int right) {
        //定义左游标
        int i = left;
        //定义右游标
        int j = right + 1;
        //定义基准元素
        int center = array[left];
        while (true) {
            //左游标右移 直到左游标大于基准元素 再接着往下走
            while (i < right && array[++i] < center) {
            }
            //右游标左移 直到右游标小于基准元素
            while(j>left && array[--j]>center){

            }
            if(i>=j){//左右游标相遇停止 跳出外部循环
                break;
            }else{
                //左右游标未相遇时停止 交换元素
                swap(array,i,j);
            }
        }
        //基准元素和游标相遇的元素交换
        swap(array,left,j);
        return j;//返回基准元素位置
    }


    public static void main(String[] args) {
        int[] array = {9, 9, 8, 7, 6, 5, 4, 3, 2, 1};
        sort(array);
        for (int i : array) {
            System.out.print(i + " ");
        }
    }

}
